In the process of developing computer programs/applications, one of the major issues is assuring appropriate levels of quality for the programs/applications. Mission critical applications require thorough testing, prior to deployment of the program/application. Applications with less reliability requirements can be built and deployed with less thorough testing. However, this causes more defects to go undetected until an end user comes across them.
On the other hand, testing effort depends on a level of complexity of the application/software under test. Even a good suit of tests driven by a human tester, covers only certain parts of the code, most of the time. In other words most of the application code is never executed in a typical scenario of manually driven testing. Testers have one or more environments in which they test the software. However, end users may have many different environments and many different applications under which a given software operates. For example, many times in an actual user environment, the software executes pieces of code which were never executed during in-house tests. This may reveal undetected defects.
To address this situation, software tests attempt to utilize measures of code coverage to cover all pieces of the code during testing process. One of such measure is line coverage or decision coverage. Line coverage counts lines of a code which were executed against all lines of the code. Decision coverage counts decisions taken during execution of decision points like, “if” statements. However, even this enhanced measure may not sufficiently cover the entire code and scenarios. Lines executed and decisions taken combined formulate execution path. One decision point with two possible decisions formulate two execution paths. But, two independent decision points with two possible decisions each formulate potentially up to 4 possible execution paths, for example, (decission1.1, decission2.1), (decission1.1, decision2.2), (decision1.2, decision2.1) and (decision1.2, decision2.2).
It is not uncommon that a defect reveals itself only on one execution path, while the rest of the execution paths remain correct. Executing each and every path in a testing environment is virtually impossible since the execution paths strongly depend, not only on UI driven actions, but also on environment, external conditions (e.g., given status of network connection), network traffic, state of a database, memory size, and the like. Emulating all such conditions is extremely time and resource consuming.
Therefore, testing is sometimes reduced to static analysis of extracted execution path. Execution paths are extracted during parsing process. Then, Control Flow Graphs (CFGs) and/or Data Flow Graphs (DFGs) are created. A code analyzer then attempts to follow the created CFGs and DFGs and detect defects. Reducing a problem to isolated, independent execution paths makes such analysis feasible. The problem with this approach is that the number of paths in a computer program is in the order of 2N, where N is number of lines of code, therefore, the analysis becomes impossibly compution intensive. As a result, this approach is impractical in large systems. There is a need to reduce the complexity of the analysis to a size which is in order of N to make the analysis practical for commercial systems in which N can be as large as 1,000,000 lines.
Therefore, there is a need for an efficient and thorough system and method for detecting defects in a computer program using data and control flow analysis.